//
// Created by Administrator on 2021/10/29.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    int maxProduct(vector<string> &words) {
        unsigned int n = words.size();
        // 按照长度排序
        sort(words.begin(), words.end(), [](string &a, string &b) {
            return a.size() > b.size();
        });
        int ans = 0;
        // 暴力  超时
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (noCross(words[i], words[j]))
                    ans = max(ans, static_cast<int>(words[i].size() * words[j].size()));
            }

        }
        return ans;
    }

    // 两个字符串是否含有相同的字母
    bool noCross(string &a, string &b) {
        unordered_set<char> s1(a.begin(), a.end());
        unordered_set<char> s2(b.begin(), b.end());
        for (auto &x: s1) {
            if (s2.count(x))
                return false;
        }
        return true;
    }
};

class Solution2 {
public:
    /**
     * 优化比较过程：一个int构成一个字符串的掩码  比较两个掩码的&结果是不是0就能知道是不是含有相同的char
     * @param words
     * @return
     */
    int maxProduct(vector<string> &words) {
        unsigned int n = words.size();
        vector<int> mask(n, 0);
        vector<int> lens(n, 0);
        for (int i = 0; i < n; ++i) {
            int bitMask = 0;
            // 构造掩码
            for (char j: words[i]) {
                bitMask |= 1 << (j - 'a');
            }
            mask[i] = bitMask;
            lens[i] = words[i].size();
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if ((mask[i] & mask[j]) == 0)
                    ans = max(ans, lens[i] * lens[j]);
            }
        }
        return ans;
    }
};
class Solution3 {
public:
    /**
     * 优化比较过程：一个int构成一个字符串的掩码  比较两个掩码的&结果是不是0就能知道是不是含有相同的char
     * 用hash存储掩码对应的长度
     * @param words
     * @return
     */
    int maxProduct(vector<string> &words) {
        unsigned int n = words.size();
        unordered_map<int,int>hashmap;
        for (int i = 0; i < n; ++i) {
            int bitMask = 0;
            // 构造掩码
            for (char j: words[i]) {
                bitMask |= 1 << (j - 'a');
            }
            hashmap[bitMask] = max((int)words[i].size(),hashmap[bitMask]);
        }
        int ans = 0;
        for(auto &x:hashmap){
            for(auto &y:hashmap){
                if ((x.first&y.first)==0)
                    ans = max(ans,x.second*y.second);
            }
        }
        return ans;
    }
};
int main() {
    vector<string> words{"abcw", "baz", "foo", "bar", "xtfn", "abcdef"};
    Solution3 solution;
    cout << solution.maxProduct(words) << endl;
    return 0;
}
